package org.basis.algorithm.practice;

import lombok.Data;

import java.util.LinkedList;

/**
 * 检查是否是二叉搜索树
 *
 * @author Mr_wenpan@163.com 2022/03/22 14:06
 */
public class CheckBinarySearchTree {

    public static void main(String[] args) {
        LinkedList<String> queue = new LinkedList<>();
        queue.addFirst("111");
        String s = queue.pollFirst();
        System.out.println(queue.size());
    }

    public static boolean isBinarySearchTree(TreeNode head) {
        if (head == null) {
            return true;
        }

        return check(head);
    }

    /**
     * 检查是否是二叉搜索树
     * 二叉搜索树：对于树上的以任意一个节点形成的一棵子树都满足：该节点一定是严格大于他的左子节点，一定严格小于他的右子节点
     * 所以，根据上面的特性，我们可以采用DFS(后序遍历)，依次检查每一棵子树是否满足上面的特点，如果整棵树上的所有子树都满足，那么该树为二叉搜索树
     * 反之，则不是二叉搜索树
     */
    public static boolean check(TreeNode node) {
        if (node == null) {
            return true;
        }
        // 问左右孩子要信息
        boolean leftRes = isBinarySearchTree(node.left);
        boolean rightRes = isBinarySearchTree(node.right);
        // 整合左右孩子的信息，并向上返回自己节点的信息（返回给自己的父节点）
        boolean flag = true;
        // node节点的值一定严格大于他的左孩子，严格小于他的右孩子
        if (node.left != null && node.val <= node.left.val) {
            flag = false;
        }
        if (node.right != null && node.val >= node.right.val) {
            flag = false;
        }
        return leftRes && rightRes && flag;
    }

    @Data
    static class TreeNode {
        Integer val;
        TreeNode left;
        TreeNode right;
    }
}
